import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    /**
     * 2025.1.10 题1：除自身以外数组的乘积
     * @param nums
     * @return
     */
    // 动态规划
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] preDp = new int[len]; // 前缀和
        int[] lastDp = new int[len]; // 后缀和
        int[] ret = new int[len];
        // 初始化
        for(int i = 0; i < len; i++) {
            preDp[i] = lastDp[i] = 1;
        }
        // 填表
        for(int i = 1; i < len; i++) {
            preDp[i] = preDp[i - 1] * nums[i - 1];
        }
        for(int i = len - 2; i >= 0; i--) {
            lastDp[i] = lastDp[i + 1] * nums[i + 1];
        }
        for(int i = 0; i < len; i++) {
            ret[i] = lastDp[i] * preDp[i];
        }
        return ret;
    }

    /**
     * 2025.1.10 题2：轮转数组
     * @param nums
     * @param k
     */
    // 使用额外的数组
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        int offset = k % len;
        int[] ret = new int[len];
        for(int i = 0; i < len; i++) {
            int index = (i + offset) % len;
            // System.out.println("nums[i]: " + nums[i] + " index: " + index);
            ret[index] = nums[i];
        }
        for(int i = 0; i < len; i++) {
            nums[i] = ret[i];
        }
    }
    // 数组翻转
    public void rotate2(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }
    // 翻转
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    /**
     * 2025.1.12 题1：旋转图形
     * @param matrix
     */
    // 数组翻转
    public void rotate(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 沿水平方向翻转
        for(int i = 0; i < m / 2; i++) {
            for(int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[m - i - 1][j];
                matrix[m - i - 1][j] = temp;
            }
        }
        // 沿正对角线方向翻转
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

    /**
     * 2025.1.11 题2：矩阵置零
     * @param matrix
     */
    // 模拟
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Map<Integer, Set<Integer>> hash = new HashMap<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    if (hash.get(i) == null) {
                        Set<Integer> set = new HashSet<>();
                        set.add(j);
                        hash.put(i, set);
                    } else {
                        hash.get(i).add(j);
                    }
                }
            }
        }
        // 置零
        for(Integer i: hash.keySet()) {
            Set<Integer> set = hash.get(i);
            for(Integer j: set) {
                for(int k = 0; k < m; k++) {
                    matrix[k][j] = 0;
                }
                for(int k = 0; k < n; k++) {
                    matrix[i][k] = 0;
                }
            }
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 2025.1.12 题1：对称二叉树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return isSymmetricRoot(root.left, root.right);
    }

    public boolean isSymmetricRoot(TreeNode leftNode, TreeNode rightNode) {
        if (null == leftNode && null == rightNode) {
            return true;
        }
        if (null == leftNode || null == rightNode || leftNode.val != rightNode.val) {
            return false;
        }
        return isSymmetricRoot(leftNode.left, rightNode.right)
                && isSymmetricRoot(leftNode.right, rightNode.left);
    }

    /**
     * 2025.1.12 题2：二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归出口
        if (null == root) {
            return null;
        }
        boolean leftP = containsNode(root.left, p);
        boolean leftQ = containsNode(root.left, q);
        if (leftP && leftQ) {
            return lowestCommonAncestor(root.left, p, q);
        } else if ((!leftP && leftQ) || (leftP &&!leftQ) || root == p || root == q) {
            return root;
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }
    private boolean containsNode(TreeNode root, TreeNode target) {
        if (null == root) {
            return false;
        }
        return (root == target)
                || containsNode(root.left, target)
                || containsNode(root.right, target);
    }

    /**
     * 2025.1.13 题1：将有序数组转换为二叉搜索树
     * @param nums
     * @return
     */
    // 递归 每次选择最中间节点作为根节点，保证左右平衡
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBSTNode(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBSTNode(int[] nums, int left, int right) {
        // 递归出口
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBSTNode(nums, left, mid - 1);
        node.right = sortedArrayToBSTNode(nums, mid + 1, right);
        return node;
    }

    /**
     * 2025.1.13 题2：和为K的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    // 动态规划（超出内存限制）二维 dp
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // 创建 dp 表
        int[][] dp = new int[len + 1][len + 1]; // 以 i 为开头，j 为结尾的序列和
        int count = 0;
        // 初始化
        // 填表
        for (int i = 1; i <= len; i++) {
            for(int j = i; j <= len; j++) {
                dp[i][j] = dp[i][j - 1] + nums[j - 1];
                if (dp[i][j] == k) {
                    count++;
                }
            }
        }
        // 返回
        return count;
    }
    /**
     * 2025.1.13 题2：和为K的子数组
     * 使用 HashMap 优化
     * @param nums
     * @param k
     * @return
     */
    // 动态规划（一维 dp）
    public int subarraySum2(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>(); // 和为 i 的序列个数
        hash.put(0, 1);
        int len = nums.length;
        int count = 0;
        // 创建 dp 表
        int[] dp = new int[len + 1];
        // 初始化
        // 填表
        for(int i = 1; i <= len; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
            count += hash.getOrDefault(dp[i] - k, 0);
            hash.put(dp[i], hash.getOrDefault(dp[i], 0) + 1);
        }
        // 返回
        return count;
    }
}

